Auxiliary data structures are used to perform operations on portions or all of a primary data structure without consuming the original data structure. For example, an auxiliary data structure may include part or all of the contents of a text document and be used to perform operations such as analysis without the original text document being consumed by the analysis application. Hence, one or more updates may need to be performed on the auxiliary data structures in response to a series of edits made to the associated primary data structure.
One approach is to update the auxiliary data structures immediately in response to each edit performed on the primary data structure. This way incremental and hence efficient updates can be performed. However, a resource cost of updating all of the auxiliary data structures right away is incurred, when in some cases the results of those computations might not be required until a later time.
Another approach is to delay updating the auxiliary data structures for as long as possible, and then recomputing their new value based on the current state of the primary data structure. Often, however, due to multiple edits having occurred, it may become difficult for this to be an incremental operation, and the update may become overly time consuming.